package com.congee02.graph;

import java.util.Arrays;

public class ValidPath_UF {

    public boolean validPath(int n, int[][] edges, int source, int destination) {

        int[] parent = new int[n];

        Arrays.setAll(parent, i -> i);

        for (int[] edge : edges) {
            union(parent, edge[0], edge[1]);
        }

        return reachable(parent, source, destination);
    }

    private boolean reachable(int[] parent, int x, int y) {
        return root(parent, x) == root(parent, y);
    }

    private int root(int[] parent, int x) {
        return parent[x] == x ? x : (parent[x] = root(parent, parent[x]));
    }

    private void union(int[] parent, int x, int y) {
        parent[root(parent, x)] = root(parent, y);
    }

}
